import java.util.Stack;

/**
 * 1028. 从先序遍历还原二叉树
 * https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/
 */
public class Solutions_1028 {
    public static void main(String[] args) {
//        String str = "1-2--3--4-5--6--7";  // output: {1, 2, 5, 3, 4, 6, 7}
//        String str = "1-2--3---4-5--6---7";  // output: {1, 2, 5, 3, null, 6, null, 4, null, 7}
        String str = "1-401--349---90--88";  // output: {1, 401, null, 349, 88, 90}

        TreeNode result = recoverFromPreorder(str);
        System.out.println(result);
    }

    /**
     * 解法二：递归（1ms）
     */
    private static int index = 0;
    public static TreeNode recoverFromPreorder(String S) {
        char[] arr = S.toCharArray();
        return dfs(arr, 0);
    }

    public static TreeNode dfs(char[] arr, int depth) {
        int level = 0;
        int val = 0;
        // 定义临时变量代替全局变量 index，因为 level != depth 时，全局变量应该没有变化
        int point = index;
        while (point < arr.length && arr[point] == '-') {
            level++;
            point++;
        }
        // 关键：通过 depth 与 level 比较，深度是否对应
        if (level != depth) {
            return null;
        }
        index = point;
        while (index < arr.length && arr[index] != '-') {
            // 计算节点值
            val = val * 10 + (arr[index] - '0');
            index++;
        }
        TreeNode root = new TreeNode(val);
        // 还原左子树
        root.left = dfs(arr, depth + 1);
        if (root.left != null) {
            // 左子树还原完成，继续还原右子树（若左子树没有，也肯定没有右子树）
            // 题目说明：如果节点只有一个子节点，那么保证该子节点为左子节点。
            root.right = dfs(arr, depth + 1);
        }
        return root;
    }

    /**
     * 解法一：迭代（模拟递归）（6ms）
     */
    public static TreeNode recoverFromPreorder2(String S) {
        // Stack 中存储是树中每一层最右侧的节点
        Stack<TreeNode> stack = new Stack<>();
        char[] arr = S.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            int level = 0;
            // 节点深度
            while (i < arr.length && arr[i] == '-') {
                i++;
                level++;
            }
            int val = arr[i] - '0';
            // 节点值
            while (i < arr.length - 1 && arr[i + 1] != '-') {
                i++;
                val = val * 10 + (arr[i] - '0');
            }
            // 找到新节点的父节点
            while (stack.size() > level) {
                stack.pop();
            }
            TreeNode node = new TreeNode(val);
            if (!stack.isEmpty()) {
                if (stack.peek().left == null) {
                    stack.peek().left = node;
                } else {
                    stack.peek().right = node;
                }
            }
            stack.push(node);
        }
        while (stack.size() > 1) {
            stack.pop();
        }
        // 返回根节点
        return stack.pop();
    }
}
